The present invention generally relates to placing cells on a programmable logic device, and more particularly, placing cells using a density surface representation.
Field programmable gate arrays (FPGAs), first introduced by XILINX in 1985, are becoming increasingly popular devices for use in electronics systems. For example, communications systems employ FPGAs in large measure for their re-programmability. In general, the use of FPGAs continues to grow at a rapid rate because they permit relatively short design cycles, reduce costs through logic consolidation, and offer flexibility in their re-programmability. The capabilities of and specifications for XILINX FPGAs are set forth in xe2x80x9cThe Programmable Logic Data Book,xe2x80x9d published in 1998 by XILINX, Inc., the contents of which is incorporated herein by reference.
The challenges facing today""s floorplanning tools are that timing constraints are becoming ever more stringent, and the number of cells to be placed is increasing rapidly. Thus, finding a feasible placement using present tools can take a very long time. Two types of processes are generally known to be used. A first type of process attempts to maintain a feasible placement throughout the placement process, and one or more selected parameters are optimized, for example, wire length and timing. While feasible placements are produced by these processes, the algorithms are generally understood to take a very long time.
A second type of placement process is termed xe2x80x9canalytical.xe2x80x9d Analytical processes treat cells as points. The first phase distributes cells over the placement area while attempting to reduce wire-length. The first phase of the analytical processes oftentimes produce a placement that is not feasible, and a subsequent phase is required to eliminate the overlaps while keeping the wire-length low. Thus, the more overlaps that remain after the first phase of the analytical process the more time the subsequent phase will require to produce a feasible placement. Thus, a process that executes quickly and that reduces the overlaps in a placement would therefore be desirable.
The method of the present invention generally uses a density surface representation of a placement in spreading cells. By considering the entire surface density, the cells can be moved in a manner that quickly minimizes the number of overlaps while keeping the wire-length low.
In one embodiment, a method is provided for analytical placement of cells using density surface representations. The placement of cells is characterized as a density surface function using a two-dimensional continuous function. The cells are iteratively moved from areas having higher densities of placed cells to areas having lower densities of placed cells using the density surface function.
The above summary of the present invention is not intended to describe each disclosed embodiment of the present invention. The figures and detailed description that follow provide additional example embodiments and aspects of the present invention.